package leetcode.daily;

import java.util.*;

public class a_20201225 {

    /**
     * 46. 全排列
     * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
     *
     * 示例:
     *
     * 输入: [1,2,3]
     * 输出:
     * [
     *   [1,2,3],
     *   [1,3,2],
     *   [2,1,3],
     *   [2,3,1],
     *   [3,1,2],
     *   [3,2,1]
     * ]
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        recurse(0, nums, result);
        return result;
    }

    private void recurse(int start, int[] nums, List<List<Integer>> result){
        if(start == nums.length-1){
            List<Integer> l = new ArrayList<>();
            for(int i : nums){
                l.add(i);
            }
            result.add(l);
        }else{
            for(int i = start; i < nums.length; i++){
                int tmp = nums[start];
                nums[start] = nums[i];
                nums[i] = tmp;
                recurse(start+1, nums, result);
                nums[i] = nums[start];
                nums[start] = tmp;
            }
        }
    }

    /**
     * 85. 最大矩形
     * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
     *
     *
     *
     * 示例 1：
     *
     *
     * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
     * 输出：6
     * 解释：最大矩形如上图所示。
     * 示例 2：
     *
     * 输入：matrix = []
     * 输出：0
     * 示例 3：
     *
     * 输入：matrix = [["0"]]
     * 输出：0
     * 示例 4：
     *
     * 输入：matrix = [["1"]]
     * 输出：1
     * 示例 5：
     *
     * 输入：matrix = [["0","0"]]
     * 输出：0
     *
     *
     * 提示：
     *
     * rows == matrix.length
     * cols == matrix[0].length
     * 0 <= row, cols <= 200
     * matrix[i][j] 为 '0' 或 '1'
     */

    public static int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int width = matrix[0].length;
        int height = matrix.length;
        /* 装换成求柱状图矩形面积
         * 例如：
         * 1   1
         * 1 1 1
         * 1 1 1
         * 纵向扫描就可以得到对应矩形面积
         */
        int[][] heights = new int[height+2][width+2]; // +2减少边界判断
        for(int i = 1; i <= height; i++){
            for(int j = 1; j <= width; j++){
                if((matrix[i-1][j-1]-'0') > 0) heights[i][j] = heights[i-1][j]+1;
            }
        }
        // 接下来按列求对应柱状图的最大面积 使用左右两个单调栈来记录其左右第一个比它小的柱位置 来减少计算复杂度
        int max = 0;
        for(int i = 1; i <= height; i++){
            int[] currHeight = heights[i];
            int[] left = new int[width+2]; // 记录左右两边第一个小于的元素位置
            int[] right = new int[width+2];
            Arrays.fill(right, width+1); // 初始化右边界数组，避免出现0
            Deque<Integer> stack = new LinkedList<>(); // 存储相应位置

            for(int j = 1; j <= width; j++){
                while (!stack.isEmpty() && currHeight[stack.peek()] >= currHeight[j]){
                    right[stack.peek()] = j; // 优化：弹出的就是右边界 减少一次扫描
                    stack.pop();
                }
                left[j] = stack.isEmpty() ? 0 : stack.peek();
                stack.push(j);
            }
            for(int j = 1; j <= width; j++){
                max = Math.max(max,
                        (right[j]-left[j]-1)*currHeight[j]);
            }
        }
        return max;
    }

    static int[] arrNums;
    static int max = 0;
    public static int maxLength(List<String> arr) {
        arrNums = new int[arr.size()];
        max = 0;
        for(int i = 0; i < arr.size(); i++){
            int a = 0;
            for(char j : arr.get(i).toCharArray()){
                if((a & 1<<j-'a') != 0){
                    a = -1;
                    break;
                }else a |= 1 << j -'a';
            }
            arrNums[i] = a;
        }
        dfs(0, 0, 0, arr);
        return max;
    }

    public static void dfs(int len, int andNum, int index, List<String> arr){
        max = Math.max(max, len);
        if(index >= arr.size()) return;
        if(arrNums[index]==-1 || (arrNums[index] & andNum) != 0){
            dfs(len, andNum, index+1, arr);
        }else{
            dfs(len+arr.get(index).length(), andNum|arrNums[index], index+1, arr);
            dfs(len, andNum, index+1, arr);
        }
    }

    /**
     * 238. 除自身以外数组的乘积
     * 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
     *
     *
     *
     * 示例:
     *
     * 输入: [1,2,3,4]
     * 输出: [24,12,8,6]
     *
     *
     * 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
     *
     * 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
     *
     * 进阶：
     * 你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
     */
    class Solution {
        public int[] productExceptSelf(int[] nums) {
            int length = nums.length;
            int[] answer = new int[length];

            // answer[i] 表示索引 i 左侧所有元素的乘积
            // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
            answer[0] = 1;
            for (int i = 1; i < length; i++) {
                answer[i] = nums[i - 1] * answer[i - 1];
            }

            // R 为右侧所有元素的乘积
            // 刚开始右边没有元素，所以 R = 1
            int R = 1;
            for (int i = length - 1; i >= 0; i--) {
                // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
                answer[i] = answer[i] * R;
                // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
                R *= nums[i];
            }
            return answer;
        }
    }


    /**
     *面试题 17.23. 最大黑方阵
     * 给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
     *
     * 返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
     *
     * 示例 1:
     *
     * 输入:
     * [
     *    [1,0,1],
     *    [0,0,1],
     *    [0,0,1]
     * ]
     * 输出: [1,0,2]
     * 解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
     * 示例 2:
     *
     * 输入:
     * [
     *    [0,1,1],
     *    [1,0,1],
     *    [1,1,0]
     * ]
     * 输出: [0,0,1]
     * 提示：
     *
     * matrix.length == matrix[0].length <= 200
     * 通过次数2,321提交次数6,485
     *
     * 下面这个解法虽然直观但是效率并不高，有一种动态规划的解法
     *
     *
     * 动态规划
     * 获取每个节点的最大黑边行和列
     * mxrow[r,c]为当前点往右的最大黑边行
     * mxcol[r,c]为当前点往下的最大黑边列
     * 从右下角开始遍历得到它们, 这样能利用之前得到的结果
     * 计算最大方阵
     * 从左上角开始遍历, 针对黑节点, 找其黑边行和列的较小值, 作为size的最大值
     * 然后递减size遍历, 如果找到一个符合条件的(右顶点和下顶点的边长度>=cursize)就break
     * 注意一个优化操作是循环遍历到当前res size+1为止, 因为如果等于当前res size的话一定不满足要求了
     *
     * 作者：suibianfahui
     * 链接：https://leetcode-cn.com/problems/max-black-square-lcci/solution/20xing-dai-ma-by-suibianfahui/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public static int[] findSquare(int[][] matrix) {
        int len = matrix.length;
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                if(matrix[i][j] == 0) queue.offer(new int[]{i, j, 1, 2});
            }
        }
        int[] tmp = new int[]{};
        while(!queue.isEmpty()){
            int[] curr = queue.poll();
            if(curr[3] == 2){
                if(tmp.length == 0) tmp = curr;
                else{
                    if(tmp[2] < curr[2]) tmp = curr;
                    else{
                        if(tmp[0] > curr[0]) tmp = curr;
                        else if((tmp[0]==curr[0]) && tmp[1]>curr[1]) tmp = curr;
                    }
                }
            }
            switch(isBlack(curr[0], curr[1], curr[2]+1, matrix)){
                case 1 : queue.offer(new int[]{
                        curr[0], curr[1], curr[2]+1, 1
                });
                    break;
                case 2 :
                    queue.offer(new int[]{
                            curr[0], curr[1], curr[2]+1, 2
                    });
                    break;
            }
        }
        return tmp.length<3 ? tmp : new int[]{tmp[0], tmp[1], tmp[2]};
    }

    private static int isBlack(int i, int j, int size, int[][] matrix){
        if(i+size-1>=matrix.length || j+size-1>=matrix.length) return 0;
        for(int l = 0; l < size; l++){
            if(matrix[i+size-1][j+l]!=0 || matrix[i+l][j+size-1]!=0) return l > 0 ? 1 : 0;
        }
        return 2;
    }

    /**
     * 1138. 字母板上的路径
     * 我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。
     *
     * 在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。
     *
     *
     *
     * 我们可以按下面的指令规则行动：
     *
     * 如果方格存在，'U' 意味着将我们的位置上移一行；
     * 如果方格存在，'D' 意味着将我们的位置下移一行；
     * 如果方格存在，'L' 意味着将我们的位置左移一列；
     * 如果方格存在，'R' 意味着将我们的位置右移一列；
     * '!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
     * （注意，字母板上只存在有字母的位置。）
     *
     * 返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。
     *
     *
     *
     * 示例 1：
     *
     * 输入：target = "leet"
     * 输出："DDR!UURRR!!DDD!"
     * 示例 2：
     *
     * 输入：target = "code"
     * 输出："RR!DDRR!UUL!R!"
     *
     *
     * 提示：
     *
     * 1 <= target.length <= 100
     * target 仅含有小写英文字母。
     */
    public String alphabetBoardPath(String target) {
        char[] c = target.toCharArray();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < c.length; i++){
            if(i == 0) {
                sb.append(getPath(0, c[i]-'a'));
            }
            else{
                sb.append(getPath(c[i-1]-'a', c[i]-'a'));
            }
        }
        return sb.toString();
    }

    private String getPath(int src, int des){
        if(src == des) return "!";
        else{
            if(src == 25) return "U"+getPath(src-5, des);
            if(des%5 < src%5){
                return "L"+getPath(src-1, des);
            }else if (des%5 > src%5){
                return "R"+getPath(src+1, des);
            }else{
                if(des < src) return "U"+getPath(src-5, des);
                else return "D"+getPath(src+5, des);
            }
        }
    }

    /**
     * 394. 字符串解码
     * 给定一个经过编码的字符串，返回它解码后的字符串。
     *
     * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
     *
     * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
     *
     * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "3[a]2[bc]"
     * 输出："aaabcbc"
     * 示例 2：
     *
     * 输入：s = "3[a2[c]]"
     * 输出："accaccacc"
     * 示例 3：
     *
     * 输入：s = "2[abc]3[cd]ef"
     * 输出："abcabccdcdcdef"
     * 示例 4：
     *
     * 输入：s = "abc3[cd]xyz"
     * 输出："abccdcdcdxyz"
     */
    public static String decodeString(String s) {
        if(s==null || s.length()==0) return "";
        else{
            if(s.charAt(0) >= '0' && s.charAt(0) <= '9'){
                int right = 0;
                int left = 0;
                int num = 0;
                int rightNum = 0;
                int leftNum = 0;
                for(int i = 0; i < s.length(); i++){
                    if (s.charAt(i)=='['){
                        left = (left==0 ? i : left);
                        leftNum++;
                    }else if(s.charAt(i) == ']') {
                        right = i;
                        rightNum++;
                    }
                    if(rightNum!=0 && rightNum==leftNum) break;
                }
                num = Integer.parseInt(s.substring(0, left));
                StringBuilder sb = new StringBuilder();
                String s1 = decodeString(s.substring(left+1, right));
                while(num > 0){
                    sb.append(s1);
                    num--;
                }
                String res = sb.toString();
                if(right == s.length()-1){
                    return res;
                }else{
                    return res + decodeString(s.substring(right+1, s.length()));
                }
            }else{
                int i = 0;
                while (i < s.length() && !(s.charAt(i) >= '0' && s.charAt(i) <= '9')){
                    i++;
                }
                return s.substring(0,i)+decodeString(s.substring(Math.min(i, s.length())));
            }
        }
    }

    /**
     * 1177. 构建回文串检测
     * 给你一个字符串 s，请你对 s 的子串进行检测。
     *
     * 每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。
     *
     * 如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。
     *
     * 返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。
     *
     * 注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）
     *
     *
     *
     * 示例：
     *
     * 输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
     * 输出：[true,false,false,true,true]
     * 解释：
     * queries[0] : 子串 = "d"，回文。
     * queries[1] : 子串 = "bc"，不是回文。
     * queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
     * queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
     * queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。
     *
     *
     * 提示：
     *
     * 1 <= s.length, queries.length <= 10^5
     * 0 <= queries[i][0] <= queries[i][1] < s.length
     * 0 <= queries[i][2] <= s.length
     * s 中只有小写英文字母
     */
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int n = s.length();
        int[] pre = new int[n];
        pre[0] = 1<<(s.charAt(0) - 'a');

        for (int i = 1; i < n; ++i) {
            pre[i] = pre[i - 1] ^ (1<<(s.charAt(i) - 'a'));
        }

        List<Boolean> ans = new ArrayList<>();
        for (int[] o: queries) {
            int tmp = pre[o[1]] ^ (o[0] == 0? 0: pre[o[0] - 1]);
            ans.add(Integer.bitCount(tmp) <= 2 * o[2] + 1);
        }
        return ans;
    }

    /**
     * 919. 完全二叉树插入器
     * 完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大）的，并且所有的节点都尽可能地集中在左侧。
     *
     * 设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
     *
     * CBTInserter(TreeNode root) 使用头节点为 root 的给定树初始化该数据结构；
     * CBTInserter.insert(int v)  向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
     * CBTInserter.get_root() 将返回树的头节点。
     *
     *
     * 示例 1：
     *
     * 输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
     * 输出：[null,1,[1,2]]
     * 示例 2：
     *
     * 输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
     * 输出：[null,3,4,[1,2,3,4,5,6,7,8]]
     *
     *
     * 提示：
     *
     * 最初给定的树是完全二叉树，且包含 1 到 1000 个节点。
     * 每个测试用例最多调用 CBTInserter.insert  操作 10000 次。
     * 给定节点或插入节点的每个值都在 0 到 5000 之间。
     */
    class CBTInserter {

        public class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }
        TreeNode root;
        Deque<TreeNode> deque;
        public CBTInserter(TreeNode root) {
            this.root = root;
            deque = new LinkedList();
            Queue<TreeNode> queue = new LinkedList();
            queue.offer(root);

            // BFS to populate deque
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node.left == null || node.right == null)
                    deque.offerLast(node);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
        }

        public int insert(int v) {
            TreeNode node = deque.peekFirst();
            deque.offerLast(new TreeNode(v));
            if (node.left == null)
                node.left = deque.peekLast();
            else {
                node.right = deque.peekLast();
                deque.pollFirst();
            }

            return node.val;
        }

        public TreeNode get_root() {
            return root;
        }
    }

    /**
     * 面试题 17.05.  字母与数字
     * 给定一个放有字符和数字的数组，找到最长的子数组，且包含的字符和数字的个数相同。
     *
     * 返回该子数组，若存在多个最长子数组，返回左端点最小的。若不存在这样的数组，返回一个空数组。
     *
     * 示例 1:
     *
     * 输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]
     *
     * 输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]
     * 示例 2:
     *
     * 输入: ["A","A"]
     *
     * 输出: []
     * 提示：
     *
     * array.length <= 100000
     *
     * 解： 由于数组中只存在字母和数字两种情况，因此我们可以将字母记为-1，数字记为1来简化问题；
     * 数组中的前缀是指从左到右，长度小于或者等于数组长度的子数组；
     * 两个前缀和的值相同，例如：prefix[i]==prefix[j]，说明[0,i]和[0,j]之间多余数字或字符的个数相同，那么如果我们用区间[0,j]减去区间[0,i]之后，在(i,j]之间的数字和字符个数必然相同，因此[(i,j]可能是一组解(注意此处得区间是左开右闭的)；
     * 前缀和为0处，例如：prefix[i]=0，说明 [0,i]之间的数字和字符个数相同，所以[0,j]可能是一组解；
     *
     * 链接：https://leetcode-cn.com/problems/find-longest-subarray-lcci/solution/mian-shi-ti-1705-zi-mu-yu-shu-zi-by-beecaffe/
     */
    public static String[] findLongestSubarray(String[] array) {

        int len = array.length;
        int[] memo = new int[(len << 1) + 1];
        Arrays.fill(memo, -2);
        memo[len] = -1;
        int res = 0, count = 0, begin = 0, end = 0;
        for (int i = 0; i < len; ++i) {
            boolean is_num = true;
            for (char c : array[i].toCharArray())
                if (c < '0' || c > '9') {
                    is_num = false;
                    break;
                }
            count += is_num ? -1 : 1;
            // 未曾见过该前缀和(即memo数组中没有记录)
            if (memo[count + len] <= -2)
                memo[count + len] = i;  // 记录该前缀和的下标
            // 曾见过该前缀和(即memo数组中已有记录)
            else if (i - memo[count + len] > res) {
                begin = memo[count + len] + 1;
                end = i + 1;
                res = i - memo[count + len];
            }
        }
        return Arrays.copyOfRange(array, begin, end);
    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    /**
     * 1123. 最深叶节点的最近公共祖先
     * 给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。
     *
     * 回想一下：
     *
     * 叶节点 是二叉树中没有子节点的节点
     * 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
     * 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。
     *
     *
     * 注意：本题与力扣 865 重复：https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/
     *
     *
     *
     * 示例 1：
     *
     *
     * 输入：root = [3,5,1,6,2,0,8,null,null,7,4]
     * 输出：[2,7,4]
     * 解释：
     * 我们返回值为 2 的节点，在图中用黄色标记。
     * 在图中用蓝色标记的是树的最深的节点。
     * 注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。
     * 示例 2：
     *
     * 输入：root = [1]
     * 输出：[1]
     * 解释：根节点是树中最深的节点，它是它本身的最近公共祖先。
     * 示例 3：
     *
     * 输入：root = [0,1,3,null,2]
     * 输出：[2]
     * 解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。
     *
     *
     * 提示：
     *
     * 给你的树中将有 1 到 1000 个节点。
     * 树中每个节点的值都在 1 到 1000 之间。
     * 每个节点的值都是独一无二的。
     * 通过次数5,380提交次数7,811
     */
    int maxDepth = 0;
    TreeNode res = null;
    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root, 0);
        return res;
    }

    /**
     *  如果两子树高度相等，则说明该节点为最大公共祖先
     *  否则的话在较深的子树之中
     **/
    private int dfs(TreeNode node, int depth){
        if(node == null) return depth;
        int right = dfs(node.right, depth+1);
        int left = dfs(node.left, depth+1);
        if(right == left && left >= maxDepth){
            maxDepth = left;
            res = node;
        }
        return Math.max(right, left);
    }

    /**
     * 67. 二进制求和
     * 给你两个二进制字符串，返回它们的和（用二进制表示）。
     *
     * 输入为 非空 字符串且只包含数字 1 和 0。
     *
     *
     *
     * 示例 1:
     *
     * 输入: a = "11", b = "1"
     * 输出: "100"
     * 示例 2:
     *
     * 输入: a = "1010", b = "1011"
     * 输出: "10101"
     *
     *
     * 提示：
     *
     * 每个字符串仅由字符 '0' 或 '1' 组成。
     * 1 <= a.length, b.length <= 10^4
     * 字符串如果不是 "0" ，就都不含前导零。
     * @param a
     * @param b
     * @return
     */
    public static String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int maxSize = Math.max(a.length(), b.length());
        int flag = 0;
        for(int i = 1; i <= maxSize; i++){
            int ai = i<=a.length() ? a.charAt(a.length()-i)-'0' : 0;
            int bi = i<=b.length() ? b.charAt(b.length()-i)-'0' : 0;
            int next = ai+bi+flag;
            if(next <= 1){
                flag = 0;
            }else{
                flag = 1;
                next -= 2;
            }
            sb.append(String.valueOf(next));
        }
        if(flag > 0) sb.append("1");
        return sb.reverse().toString();
    }





    public static void main(String[] args){
//        System.out.println(maximalRectangle(new char[][]{
//                new char[]{'1','0','1','0','0'},
//                new char[]{'1','0','1','1','1'},
//                new char[]{'1','1','1','1','1'},
//                new char[]{'1','0','0','1','0'},
//        }));
//        System.out.println(maximalRectangle(new char[][]{
//                new char[]{'1','1'},
//        }));

//        List<String> l = new LinkedList<>();
//        l.add("aa");
//        l.add("bkhwmpbiisbldzknp");
//
//        System.out.println(maxLength(l));

//        System.out.println(Arrays.toString(findSquare(new int[][]{
//                new int[]{1,0,1},
//                new int[]{0,0,1},
//                new int[]{0,0,1},
//        })));
//        System.out.println(canMakePaliQueries("abcda", new int[][]{
//                new int[]{3,3,0},
//                new int[]{1,2,0},
//                new int[]{0,3,1},
//                new int[]{0,3,2},
//                new int[]{0,4,1},
//        }));
//        System.out.println(Arrays.toString(findLongestSubarray(new String[]{
//                "A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"
//        })));
        System.out.println(addBinary("11", "1"));
    }
}
